As integrated circuits are produced with greater and greater levels of circuit density, efficient testing schemes that guarantee high fault coverage while minimizing test costs and chip area overhead have become essential. The number of transistors that can be placed on a chip has been doubling roughly every eighteen months, as predicted by Moore's law. The amount of data required to test such massively complex chips has been increasing even more rapidly. In practical terms, for very large integrated circuits, the test cost is approaching (and may even exceed) the design cost.
Various algorithms that employ various schemes related to testing are implemented as software code within testing software. These include such algorithms as those related to automated test pattern generation and fault simulation, for instance. Improving the speed of performance of such algorithms can help reduce costs and time associated with preparing to test a circuit.
Some of the automated circuit testing algorithms relate to various schemes for generating test patterns. A test pattern comprises a set of specified values for a circuit's inputs and scan elements that is created to detect one or more faults of the circuit and possibly satisfying one or more sets of constraints on the values of the circuit. It may specify values for a subset of the inputs and scan elements (e.g., a test cube) or all of them (possibly a test cube with pattern fill). It may also optionally include information about expected circuit output and scan element values.
Automatic test pattern generation (ATPG) is typically performed in the following manner. To generate a test pattern to be included in a test set, one or more faults related to the circuit under test (CUT) from a list of targeted faults are selected and a test pattern configured to detect the targeted faults is computed. The deterministic test values in the test pattern comprise values generated to provoke the targeted faults and cause their effects to be propagated to a point where they can be observed. These deterministic test patterns are sometimes referred to as “test cubes.” Typically, the deterministic test values comprise only a small portion of the test values in a test pattern. In some cases, for example, only 1% to 5% of the values in a test pattern are deterministic values for testing targeted faults. The remaining, unspecified values are typically filled with randomly selected values as pattern fill used to fully specify the test pattern for fault simulation and other forms of testing. In some cases, instead of random values, constant “0”s or “1”s are chosen. In still other cases, values that minimize power dissipation are used. Fault simulation is then performed to determine which of the faults are detected and can be dropped from further consideration (e.g., removed from the list of targeted faults). This procedure is iterated until all faults have been targeted and detected.
In test environments that use encoding or other methods of data compression to reduce test data volume (such as embedded deterministic test), the unspecified values in a test pattern can also be randomly filled by a decompressor during the process of test loading the test stimuli. The fully specified pattern resulting from decompression can be simulated during test pattern generation in order to determine what faults are detected by the test pattern and can be dropped from the list of targeted faults.
In random test pattern generation, random patterns are created and simulated to determine which faults they detect, with additional patterns being generated until either a desired test coverage is reached or it appears that the possible benefits of the additional coverage is outweighed by the effort required to achieve it. In deterministic test pattern generation one or more specific faults are targeted. First, the conditions necessary to cause those faults to affect the circuit are determined (referred to as fault excitation), and a search algorithm is employed to deterministically justify those conditions while propagating the effects of the fault to an observation point such as a circuit output or a scan cell (fault propagation). These two techniques are often combined in various ways, for example by using random test generation to limit the number of faults that need to be targeted deterministically, or by filling in unspecified portions of deterministically generated patterns with random values (e.g., by pattern fill)
Test pattern generation algorithms are often accessed based on three properties. First, the overall fault coverage achieved, (e.g., measured as a percentage of modeled faults that the patterns will detect). Second, the number of test patterns generated (pattern count); and third, the time required to generate the patterns. High fault coverage is important as a measure of the benefit of applying the patterns to a device since the higher the coverage of the faults being targeted the more likely the patterns are to be able to detect a corresponding manufacturing defect in the device.
Low pattern count is important for keeping the cost of applying the patterns to the devices low. Many methods are used to reduce the number of patterns generated by test pattern generation algorithms. For instance, simulation-based compaction can be used to determine which faults are detected by test patterns, allowing a minimal set of test patterns to be chosen to cover all the faults. Trade offs such as sacrificing fault coverage for lower pattern count can be made, if desired, by eliminating patterns that do not contribute much additional fault coverage. In practice, this can be quite computationally expensive. It is more common to simulate the generated patterns in different orders, often including reverse order, eliminating patterns that only detect faults already detected by patterns already simulated.
Another effective method of reducing the overall pattern count is via dynamic test compaction within the algorithm itself. In dynamic test compaction, one or more faults are targeted deterministically by the test pattern generation algorithm, then the resulting partially specified pattern is enhanced by targeting additional faults incrementally subject to the restrictions already determined to be necessary to detect the previous faults. If the test pattern generation algorithm is successful at detecting the incrementally targeted fault or faults, then the enhanced test pattern is used as a starting point for incrementally targeting even more faults, until some stopping threshold condition is reached. If the algorithm is unsuccessful, then the original pattern is reused as a starting point for targeting other faults, again until some stopping point is reached. In this manner, each generated pattern targets multiple faults, and thus, reduces the overall pattern count.
It should be noted that incrementally targeting faults subject to previously imposed constraints can reduce the overall search space for a successful test. This can result in reduced computational effort while also reducing the probability of success. Hence, it is may be necessary to incrementally target a given fault a number of times before a successful result is obtained. Furthermore, pattern count (and computational efficiency) can also be further improved by not targeting faults already detected by previously generated patterns, and by not incrementally targeting faults already detected by any current partially specified test pattern. Ideally, this would involve simulating each partially specified pattern against the entire fault list to drop detected faults from consideration, but this is not practical computationally. At best it is practical to simulate on a per-pattern basis. In fact, many testing algorithms incorporate simulation techniques that are more efficient simulating multiple patterns at once (e.g., 32 or 64 at a time).
So instead of simulating each pattern individually to drop faults from consideration, simulation may occur less frequently, and patterns or partial patterns are generated in many cases that are not needed. This increases the overall test pattern generation computational effort and pattern count in favor of overall efficiency. Testing algorithms attempt to limit this redundant overlap of patterns by targeting faults using an ordering based partially on random number generators, either when creating the initial partial pattern and/or during subsequent targeting, which reduces the chances of generating patterns that target similar faults. These random number generators can be pseudo random number generators. The random number generators used deterministically generate random number sequences that can be repeated if desired by setting the seed (i.e. the state) of the generator to a specific value.
The time required to generate the patterns is important both in terms of the cost of generating the patterns and in terms of reducing the time required to get a device to market. Shortening the time can also allow more experimentation with other parameters of a device to occur, allowing improved device quality or functionality in a fixed development schedule. This applies in general to circuit testing algorithms that include not only test pattern generation algorithms but other algorithms related to such circuit testing activities as fault simulation, and test pattern compaction. As noted above, executing these various testing algorithms is complex and computationally time consuming at least in part because of the complex schemes involved in these algorithms. One way to reduce the time associated with test pattern generation is by employing multiple computer processors (on one or more host computers) to perform algorithms associated with test pattern generation.